package leetcode.code;

import java.util.List;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution638_1 implements IDebug {

	private int[] prices;
	private int[] need;
	private int[][] specials;
	private int n;
	private int m;

	public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
		n = price.size();
		m = special.size();
		prices = new int[n];
		need = new int[n];
		specials = new int[m + n][n + 1];
		int i = 0;
		for (int num : price) {
			prices[i++] = num;
		}
		i = 0;
		for (int num : needs) {
			need[i++] = num;
		}
		i = 0;
		for (List<Integer> s : special) {
			int j = 0;
			for (int num : s) {
				specials[i][j++] = num;
			}
			i++;
		}
		for (int j = 0; j < n; j++) {
			specials[i][j] = 1;
			specials[i][n] = prices[j];
			i++;
		}
		return this.shoppingOffers(0);
	}

	private Integer shoppingOffers(int index) {// 买第几样东西, 从 0 到最多的尽可能尝试
		if (index == m + n) {
			for (int num : need) {
				if (num != 0)
					return null;
			}
			return 0;
		}
		int[] special = this.specials[index];
		Integer ans = null;
		int num = 0;
		while (true) {
			int price = special[n] * num;
			for (int i = 0; i < n; i++) {
				need[i] -= special[i] * num;
				if (need[i] < 0) {
					for (int j = i; j >= 0; j--) {
						need[j] += special[j] * num;
					}
					return ans;
				}
			}
			Integer sub = shoppingOffers(index + 1);
			if (sub != null) {
				int cur = price + sub;
				if (ans == null) {
					ans = cur;
				} else {
					ans = Math.min(ans, cur);
				}
			}
			for (int i = 0; i < n; i++) {
				need[i] += special[i] * num;
			}
			num++;
		}
	}

	@Override
	public void debug1() {
		String str = "[2,5]";
		List<Integer> price = HelpDebug.str2intlist(str);
		String str1 = "[[3,0,5],[1,2,10]]";
		List<List<Integer>> special = HelpDebug.str2intlist1(str1);
		String str2 = "[3,2]";
		List<Integer> needs = HelpDebug.str2intlist(str2);
		int e = 14;
		int r = this.shoppingOffers(price, special, needs);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		String str = "[2,3,4]";
		List<Integer> price = HelpDebug.str2intlist(str);
		String str1 = "[[1,1,0,4],[2,2,1,9]]";
		List<List<Integer>> special = HelpDebug.str2intlist1(str1);
		String str2 = "[1,2,1]";
		List<Integer> needs = HelpDebug.str2intlist(str2);
		int e = 11;
		int r = this.shoppingOffers(price, special, needs);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution638_1 so = new Solution638_1();
		so.debug1();
		so.debug2();

	}

}
